package org.laizili.solution.leetcode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * <a href="https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters/">316. 去除重复字母</a>
 * <p>
 * tags: 单调栈; 贪心
 * </p>
 *
 * @see <a href="https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters">1081. 不同字符的最小子序列</a>
 */
public class Problem316 {
    // 维护单调栈
    private static class Solution {
        private static final int TABLE_LENGTH = 26;

        private int computeHash(char ch) {
            return ch - 'a';
        }

        public String removeDuplicateLetters(String s) {
            char[] charArray = s.toCharArray();
            int len = s.length();
            int[] lashIndex = new int[TABLE_LENGTH];
            for (int i = 0; i < len; i++) {
                lashIndex[computeHash(charArray[i])] = i;
            }
            boolean[] visited = new boolean[TABLE_LENGTH];
            Deque<Character> stack = new ArrayDeque<>();
            for (int i = 0; i < len; i++) {
                char ch = charArray[i];
                int hc = computeHash(ch);
                if (visited[hc]) {
                    // 已入栈
                    continue;
                }
                while (!stack.isEmpty() && stack.peekFirst() > ch && i < lashIndex[computeHash(stack.peekFirst())]) {
                    char och = stack.removeFirst();
                    visited[computeHash(och)] = false;
                }
                stack.push(ch);
                visited[hc] = true;
            }
            StringBuilder sb = new StringBuilder();
            stack.descendingIterator().forEachRemaining(sb::append);
            return sb.toString();
        }
    }
}
